package leetcode9;

public class test49 {
    /**
     * 207. 课程表
     * @param numCourses
     * @param prerequisites
     * @return
     */
    //拓扑排序
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 创建一个映射，记录每个课程的后置课程
        Map<Integer, List<Integer>> map = new HashMap<>();
        // 创建一个数组，用于记录每个课程的入度（前置课程数量）
        int[] inDegree = new int[numCourses];

        // 初始化映射，确保每个课程都有一个空的后置课程列表
        for (int i = 0; i < numCourses; i++) {
            map.put(i, new ArrayList<>());
        }

        // 填充入度数组和后置课程映射
        for (int[] p : prerequisites) {
            inDegree[p[0]]++; // 课程 p[0] 的入度增加
            map.get(p[1]).add(p[0]); // 课程 p[1] 的后置课程添加 p[0]
        }

        // 创建一个队列，用于存放所有入度为 0 的课程
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i); // 将入度为 0 的课程加入队列
            }
        }

        // 处理队列中的课程
        while (!queue.isEmpty()) {
            // 获取当前队列的大小
            for (int i = queue.size() - 1; i >= 0; i--) {
                Integer temp = queue.poll(); // 取出队头课程
                numCourses--; // 已完成的课程数量减少

                // 获取当前课程的后置课程
                List<Integer> lists = map.get(temp);
                for (Integer list : lists) {
                    inDegree[list]--; // 将后置课程的入度减 1
                    // 如果后置课程的入度变为 0，则加入队列
                    if (inDegree[list] == 0) {
                        queue.offer(list);
                    }
                }
            }
        }

        // 如果所有课程都能完成，则返回 true
        return numCourses == 0;
    }

}
